package org.example.myleet.p801;

public class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        //0-本回合不交换情况下的操作数, 1-本回合交换情况下的操作数
        int[][] dp = new int[n][2];
        //第一回合可以交换也可以不交换，如果交换了的话，后面的每一步会根据前一步进行调整
        dp[0][1] = 1;
        for (int i = 1; i < n; ++i) {
            //题目保证必定能操作，因此，要么满足情况1要么满足情况2，要么两种情况都满足
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                //不用交换就能保持递增，则不交换的情况下保持操作次数；这一回合交换的情况则是由于上一回合交换过的结果，要交换回来，并增加操作数1
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = dp[i - 1][1] + 1;
            }
            if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
                //需要交换才能保持递增，则不交换的情况下是由于上一回合交换才能保持递增，因此保持上一回合交换过的操作次数；这一回合交换的情况则是由于上一回合没交换过，需要交换并增加操作数1
                dp[i][0] = dp[i - 1][1];
                dp[i][1] = dp[i - 1][0] + 1;
            }
            if ((nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) && (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i])) {
                //如果两种情况都符合，则继承操作数小的情况
                dp[i][0] = Math.min(dp[i - 1][0], dp[i - 1][1]);
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
            }
        }
        return Math.min(dp[n - 1][0], dp[n - 1][1]);
    }
}
